package 力扣_树算法.二叉树;

import java.util.Deque;
import java.util.LinkedList;

/**111.二叉树的最小深度
 * @author zx
 * @create 2022-04-10 21:30
 */
public class Num111 {
    /**
     * 递归法，相比求MaxDepth要复杂点
     * 因为最小深度是从根节点到最近**叶子节点**的最短路径上的节点数量
     */
    public int minDepth1(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int leftDepth = minDepth(root.left);
        int rightDepth = minDepth(root.right);
        //如果左子树为空，右子树不为空，说明最小深度是 1 + 右子树的深度。
        if (root.left == null && root.right != null) {
            return rightDepth + 1;
        }
        //右子树为空，左子树不为空，最小深度是 1 + 左子树的深度
        if (root.right == null && root.left != null) {
            return leftDepth + 1;
        }
        //左右子树都不为空，返回左右子树深度最小值 + 1
        return Math.min(leftDepth, rightDepth) + 1;
    }

    /**
     * 因为层次遍历是按照从上到下且每层从左到右的顺序访问的,如果待返回节点是叶子结点,
     * 说明当前层和之前的所有层都没有出现过叶子结点(不然就返回了),所以第一个搜索到的叶子结点深度一定是最小的
     * @return
     */
    public static int minDepth2(TreeNode root) {
        if (root == null) {
            return 0;
        }
        Deque<TreeNode> deque = new LinkedList<>();
        deque.offer(root);
        int level = 1;
        while (!deque.isEmpty()) {
            int size = deque.size();
            for (int i = 0; i < size; i++) {
                TreeNode cur = deque.poll();
                if (cur.right == null && cur.left == null){
                    return level;
                }
                if (cur.left!=null){
                    deque.offer(cur.left);
                }
                if (cur.right!=null){
                    deque.offer(cur.right);
                }
            }
            level++;
        }
        return level;
    }

    /**
     * 精简之后的代码根本看不出是哪种遍历方式，所以依然还要强调一波：
     * 如果对二叉树的操作还不熟练，尽量不要直接照着精简代码来学。
     * @return 递归写法一
     */
    public int minDepth(TreeNode root) {
        if(root == null){
            return 0;
        }
        if(root.left == null){
            return 1 + minDepth(root.right);
        }else if(root.right == null){
            return 1 + minDepth(root.left);
        }
        return 1 + Math.min(minDepth(root.left),minDepth(root.right));
    }
}
